package com.itheima.datastructure.stack;

import com.itheima.datastructure.queue.ArrayQueue3;
import com.itheima.datastructure.queue.Queue;

/**
 * 单队列模拟栈
 * <ol>
 *     <li>调用 push、pop 等方法的次数最多 100</li>
 *     <li>每次调用 pop 和 top 都能保证栈不为空</li>
 * </ol>
 */
public class E05Leetcode225 {
    /*

        栈顶      栈底
        d    c    b    a
        队列头    队列尾

        queue.offer(a)
        queue.offer(b)
        queue.offer(c)

        push 添加
            - 将新加入元素，前面的所有元素从队列头移动到队列尾
        pop 移除
            - 直接移除队列头元素

     */

    ArrayQueue3<Integer> queue = new ArrayQueue3<>(100);
    private int size = 0;

    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
        size++;
    }

    public int pop() {
        size--;
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }



    static class ArrayQueue3<E> {
        private E[] array;
        int head = 0;
        int tail = 0;

        @SuppressWarnings("all")
        public ArrayQueue3(int c) {
            // 1. 抛异常
     /*   if ((capacity & capacity-1) == 0) {
            throw new IllegalArgumentException("capacity必须是2的幂");
        }*/

            // 2. 改为2^n, 13 -> 16  22 -> 32
            c -= 1;
            c |= c >> 1;
            c |= c >> 2;
            c |= c >> 4;
            c |= c >> 8;
            c |= c >> 16;
            c += 1;

            array = (E[]) new Object[c];
        }

    /*
        求模运算：
        - 如果除数是 2 的 n 次方
        - 那么被除数的后 n 位即为余数 (模)
        - 求被除数的后 n 位方法： 与 2^n-1 按位与
     */

        public boolean offer(E value) {
            if (isFull()) {
                return false;
            }
//        array[(int) (Integer.toUnsignedLong(tail) % array.length)] = value;
            array[tail & array.length - 1] = value;
            tail++;
            return true;
        }

        public E poll() {
            if (isEmpty()) {
                return null;
            }
//        E value = array[(int) (Integer.toUnsignedLong(head) % array.length)];
            E value = array[head & array.length - 1];
            head++;
            return value;
        }

        public E peek() {
            if (isEmpty()) {
                return null;
            }
//        return array[(int) (Integer.toUnsignedLong(head) % array.length)];
            return array[head & array.length - 1];
        }

        public boolean isEmpty() {
            return head == tail;
        }

        public boolean isFull() {
            return tail - head == array.length;
        }

    }

}
/*    ArrayQueue3<Integer> queue = new ArrayQueue3<>(100);
    private int size = 0;

    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
        size++;
    }

    public int pop() {
        size--;
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }*/
